package bc;

public class lc1319 {
    static class UF{
        int count;
        int[] father;
        int[] Size;

        public UF(int n) {
            this.count = n;
            father = new int[n];
            Size = new int[n];
            for (int i = 0; i < n; i++) {
                father[i] = i;
                Size[i] = 1;
            }
        }
        public int getFather(int i){
            if(i == father[i])
                return i;
            return getFather(father[i]);
        }

        public int getCount() {
            return count;
        }
        public void uniform(int i, int j){
            int p = getFather(i);
            int q = getFather(j);
            if(p == q)
                return;
            if(Size[p] > Size[q]){
                father[q] = p;
                Size[p] += Size[q];
            }
            else {
                father[p] = q;
                Size[q] += Size[p];
            }
            count--;
        }
    }

    public static void main(String[] args) {
        System.out.println(makeConnected(6, new int[][]{{0,1},{0,2},{0,3},{1,2},{1,3}}));
    }
    public static int makeConnected(int n, int[][] connections) {
        if (connections.length < n - 1)
            return -1;        // n 个节点相互连通至少需要n-1条线
        UF uf = new UF(n);
        for (int[] connect : connections) {
            uf.uniform(connect[0], connect[1]);  // 合并
        }
        return uf.getCount() - 1;
    }
}
